Teleporty

Limit pamięci: 64 MB

Król Bajtazar włada całym układem słonecznym, w którym znajduje się planet. Planety te są ponumerowane od 1 do . Jego pałac znajduje się na planecie nr 1, zaś jego baza wojskowa na planecie nr 2. Dawno temu Bajtazar wybudował teleport, który w ciągu dwustu pięćdziesięciu minut (czyli nieco ponad czterech godzin) jest w stanie przenieść go z planety nr 1 na planetę nr 2 lub z powrotem.

Obecnie dostępna jest bardziej zaawansowana technologia, która umożliwia tworzenie teleportów zapewniających transport między dwiema planetami w czasie jednej godziny (teleporty takie są z natury dwukierunkowe). Niektóre planety układu są już połączone takimi teleportami. Teleporty te umożliwiają przebycie trasy pomiędzy planetami 1 i 2, na szczęście nie szybciej niż prywatny teleport Bajtazara (co oczywiście zagrażałoby jego bezpieczeństwu).

Obecnie każda para planet, która nie jest jeszcze bezpośrednio połączona teleportem nowej generacji, złożyła wniosek o utworzenie łączącego ich takiego teleportu. Bajtazar chce się zgodzić na jak największą liczbę takich wniosków, ale tak, aby ciągle nie dało się pokonać trasy z planety nr 1 do 2 szybciej niż przy pomocy jego prywatnego teleportu. Pomóż mu określić, na ile nowych teleportów może się zgodzić.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę planet w królestwie Bajtazara oraz liczbę istniejących teleportów nowej generacji. W kolejnych wierszach opisane są już istniejące teleporty. W każdym z tych wierszy znajdują się po dwie liczby całkowite i () oddzielone pojedynczym odstępem, oznaczające, że istnieje teleport łączący planety i . Każda para liczb występuje na wejściu co najwyżej raz. Możesz założyć, że istniejące teleporty umożliwiają przedostanie się z planety nr 1 na planetę nr 2, ale nie w czasie krótszym niż 250 minut.

Wyjście

Twój program powinien wypisać w pierwszym wierszu standardowego wyjścia jedną liczbę całkowitą, oznaczającą maksymalną liczbę nowych teleportów, na utworzenie których może zgodzić się Bajtazar.

Przykład

Dla danych wejściowych:

10 10
1 3
3 5
5 7
7 9
2 9
1 4
4 6
6 8
8 10
2 10

poprawną odpowiedzią jest:

10

Linią ciągłą na rysunku zaznaczono istniejące teleporty, a przerywaną te, na budowę których Bajtazar może pozwolić.

Autor zadania: Jakub Onufry Wojtaszczyk.